package jm.algorithm.dp;

/**
 * @Description 最长公共子序列
 * @date 2022/5/24 14:53
 */
public class LCS {

    public static void main(String[] args) {
        int[] nums1 = {1, 3, 5, 9, 10};
        int[] nums2 = {1, 9, 10};
        System.out.println(new LCS().lcs4(nums1, nums2));
    }

    /**
     * dp 最长公共子序列
     * @param nums1
     * @param nums2
     * @return
     */
    public int lcs1(int[] nums1, int[] nums2){
        if (nums1 == null || nums1.length == 0) return 0;
        if (nums2 == null || nums2.length == 0) return 0;

        // 定义dp长度，dp[0][j] 和 dp[i][0] 都默认为 0 不需要处理
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];

        // 直接从 1 开始处理
        for (int i = 1; i <= nums1.length; i++) {
            for (int j = 1; j <= nums2.length; j++) {
                if (nums1[i -1] == nums2[j -1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        // 二维dp中最后一个元素，就分别是 n1 和 n2 的最后一个元素
        return dp[nums1.length][nums2.length];
    }


    /**
     * dp 最长公共子序列 - 滚动数组优化
     * @param nums1
     * @param nums2
     * @return
     */
    public int lcs2(int[] nums1, int[] nums2){
        if (nums1 == null || nums1.length == 0) return 0;
        if (nums2 == null || nums2.length == 0) return 0;

        // 保存两行数据
        int[][] dp = new int[2][nums2.length + 1];

        for (int i = 1; i <= nums1.length; i++) {
            // & 1 等同于 % 2
            int row = i & 1;
            // 当前行的前一个元素
            int prevRow = (i - 1) & 1;
            for (int j = 1; j <= nums2.length; j++) {
                if (nums1[i - 1] == nums2[j -1]){
                    dp[row][j] = dp[prevRow][j - 1] + 1;
                }else {
                    dp[row][j] = Math.max(dp[prevRow][j],dp[row][j-1]);
                }
            }
        }
        return dp[nums1.length & 1][nums2.length];
    }

    /**
     * dp 最长公共子序列 - 一维数组优化
     * @param nums1
     * @param nums2
     * @return
     */
    public int lcs3(int[] nums1, int[] nums2){
        if (nums1 == null || nums1.length == 0) return 0;
        if (nums2 == null || nums2.length == 0) return 0;
        int[] dp = new int[nums2.length + 1];

        for (int i = 1; i <= nums1.length; i++) {
            // 中间变量
            // 作为下一次计算的 leftTop
            int cur = 0;
            for (int j = 1; j <= nums2.length; j++) {
                // 当前行循环中，默认初始为中间变量
                int leftTop = cur;
                cur = dp[j];
                if (nums1[i - 1] == nums2[j -1]){
                    dp[j] = leftTop + 1;
                }else {
                    // 将心的最大值覆盖掉原先的dp[j]
                    dp[j] = Math.max(dp[j],dp[j - 1]);
                }
            }
        }
        return dp[nums2.length];
    }

    /**
     * dp 最长公共子序列 - 行列优化
     * @param nums1
     * @param nums2
     * @return
     */
    public int lcs4(int[] nums1, int[] nums2){
        if (nums1 == null || nums1.length == 0) return 0;
        if (nums2 == null || nums2.length == 0) return 0;
        int[] rowsNums = nums1, colsNums = nums2;
        if (nums1.length < nums2.length){
            colsNums = nums1;
            rowsNums = nums2;
        }

        int[] dp = new int[colsNums.length + 1];

        for (int i = 1; i <= rowsNums.length; i++) {
            // 中间变量
            // 作为下一次计算的 leftTop
            int cur = 0;
            for (int j = 1; j <= colsNums.length; j++) {
                // 当前行循环中，默认初始为中间变量
                int leftTop = cur;
                cur = dp[j];
                if (rowsNums[i - 1] == colsNums[j -1]){
                    dp[j] = leftTop + 1;
                }else {
                    // 将心的最大值覆盖掉原先的dp[j]
                    dp[j] = Math.max(dp[j],dp[j - 1]);
                }
            }
        }
        return dp[colsNums.length];
    }

    /**
     * leet-code 1143 lcs
     * @param text1
     * @param text2
     * @return
     */
    public int longestCommonSubsequence(String text1, String text2) {
        if (text1 == null || text2 == null) return 0;
        char[] c1 = text1.toCharArray();
        char[] c2 = text2.toCharArray();
        if (c1.length == 0 || c2.length == 0) return 0;

        char[] rowsNums = c1, colsNums = c2;
        if (c1.length < c2.length){
            colsNums = c1;
            rowsNums = c2;
        }

        int[] dp = new int[colsNums.length + 1];

        for (int i = 1; i <= rowsNums.length; i++) {
            // 中间变量
            // 作为下一次计算的 leftTop
            int cur = 0;
            for (int j = 1; j <= colsNums.length; j++) {
                // 当前行循环中，默认初始为中间变量
                int leftTop = cur;
                cur = dp[j];
                if (rowsNums[i - 1] == colsNums[j -1]){
                    dp[j] = leftTop + 1;
                }else {
                    // 将心的最大值覆盖掉原先的dp[j]
                    dp[j] = Math.max(dp[j],dp[j - 1]);
                }
            }
        }
        return dp[colsNums.length];
    }
}
